#include "dbg.h"
#include "dominion_helpers.h"
#include "rngs.h"
#include <assert.h>
#include <math.h>
#include <search.h>

void copy_state(struct gameState *dest, struct gameState *src)
{
    memcpy(dest, src, sizeof(struct gameState));
}

int get_first_in_pile(int *pile, int pile_size, int card)
{
    //int card_count = 0;
    int i;

    for(i = 0; i < pile_size; i++)
        if(pile[i] == card)
            return i;

    return -1;
}

int count_cards(int *pile, int pile_size, int card)
{
    int card_count = 0;
    int i;

    for(i = 0; i < pile_size; i++)
        if(pile[i] == card)
            card_count++;

    return card_count;
}

int count_cards_of_type(int *pile, int pile_size, int card_t)
{
    int card_count = 0;
    int i;

    for(i = 0; i < pile_size; i++)
        if(get_card_type(pile[i]) == card_t)
            card_count++;

    return card_count;
}


int get_total_card_counts(struct gameState *state, int card_counts[NUM_TOTAL_K_CARDS])
{
    int num_players = state->numPlayers;
    int total_count = 0;
    int i, j;

    for(i = 0; i < NUM_TOTAL_K_CARDS; i++)
        card_counts[i] = 0;

    for(i = 0; i < num_players; i++) {
        for(j = 0; j < state->handCount[i]; j++) {
            card_counts[state->hand[i][j]]++;
            total_count++;
        }
        for(j = 0; j < state->deckCount[i]; j++) {
            card_counts[state->deck[i][j]]++;
            total_count++;
        }
        for(j = 0; j < state->discardCount[i]; j++) {
            card_counts[state->discard[i][j]]++;
            total_count++;
        }
    }

    for(i = 0; i < NUM_TOTAL_K_CARDS; i++) {
        if(state->supplyCount[i] != -1) {
            card_counts[i] += state->supplyCount[i];
            total_count += state->supplyCount[i];
        }
    }

    return total_count;
}

void shuffle_game(int player, struct gameState *state)
{
    // Make sure state has been allocated already
    assert(state != NULL);

    int num_players = state->numPlayers;

    // Make sure players is a valid value
    assert(num_players >=2 && num_players <= MAX_PLAYERS);

    char card_name[MAX_STRING_LENGTH];
    int card_counts[NUM_TOTAL_K_CARDS];
    int card_pos;
    int insert_count;
    int init_total_card_count, post_total_card_count;
    int *all_cards, *shuffled_cards;
    int all_cards_count = 0, shuffled_cards_count = 0;
    int i, j;

    init_total_card_count = get_total_card_counts(state, card_counts);

    all_cards = malloc(init_total_card_count * sizeof(int));
    shuffled_cards = malloc(init_total_card_count * sizeof(int));

    // Copy all cards into flat list
    for(i = 0; i < NUM_TOTAL_K_CARDS; i++) {
        for(j = 0; j < card_counts[i]; j++) {
            all_cards[all_cards_count] = i;
            all_cards_count++;
        }
    }

    check(all_cards_count == init_total_card_count, "failed to copy all cards to flat list");

    // Reduce state card counts to 0
    for(i = 0; i < NUM_TOTAL_K_CARDS; i++)
        if(state->supplyCount[i] != -1)
            state->supplyCount[i] = 0;

    for(i = 0; i < num_players; i++) {
        state->deckCount[i] = 0;
        state->handCount[i] = 0;
        state->discardCount[i] = 0;
    }

    /* SORT CARDS TO ENSURE DETERMINISM! */
    qsort ((void*)all_cards, all_cards_count, sizeof(int), compare);

    // Shuffle all cards
    for(i = 0; i < init_total_card_count; i++) {
        // Get a random number in between 0 and the maximum current index of
        // the all_cards array.
        card_pos = randRange(0, all_cards_count - 1);
        // Move the card at that index to the shuffled_cards array.
        cardNumToName(all_cards[card_pos], card_name);
        shuffled_cards[shuffled_cards_count] = all_cards[card_pos];
        // Increment the index of next insertion.
        shuffled_cards_count++;
        // Move all cards above the current position in all_cards down by one
        // position
        for(j = card_pos; j < all_cards_count - 1; j++)
            all_cards[j] = all_cards[j + 1];
        // Decrement the maximum index for all_cards
        all_cards_count--;
    }

    check(shuffled_cards_count == init_total_card_count, "failed to copy all cards to shuffled list");

    // Insert random numbers of cards from shuffled_cards into different
    // players' decks and discard piles.
    //
    // We use HANDSIZE as the minimum number of cards to insert into the
    // player's deck in order to ensure that each player can draw at least one
    // full hand.
    for(i = 0; i < num_players; i++) {
        if(shuffled_cards_count == 0)
            break;

        // Insert cards into player's deck
        insert_count = randRange(HANDSIZE, shuffled_cards_count);

        for(j = 0; j < insert_count; j++) {
            if(shuffled_cards_count == 0)
                break;
            state->deck[i][j] = shuffled_cards[shuffled_cards_count - 1];
            state->deckCount[i]++;
            shuffled_cards_count--;
        }

        // Insert cards into player's discard pile
        state->deckCount[i] = insert_count;
        insert_count = randRange(0, shuffled_cards_count);

        for(j = 0; j < insert_count; j++) {
            if(shuffled_cards_count == 0)
                break;
            state->discard[i][j] = shuffled_cards[shuffled_cards_count - 1];
            state->discardCount[i]++;
            shuffled_cards_count--;
        }
        state->discardCount[i] = insert_count;
    }

    // Place remaining cards in supply
    for(i = 0; i < shuffled_cards_count; i++)
        state->supplyCount[shuffled_cards[i]]++;

    post_total_card_count = get_total_card_counts(state, card_counts);
    check(post_total_card_count = init_total_card_count, "failed to copy all cards to new play state");

error:
    free(all_cards);
    free(shuffled_cards);
}

void randState(struct gameState *state, int mandatory_card, int phase)
{
    // Make sure state has been allocated already
    assert(state != NULL);
    // Make sure that the card is valid
    assert(mandatory_card >= curse && mandatory_card <= treasure_map);
    // Make sure that the phase is valid
    assert(phase >= action && phase <= cleanup);

    //memset(state, 0, sizeof(struct gameState));

    // Get a random number of players from 2-4
    int num_players = randRange(2, MAX_PLAYERS);
    // Set current player to a number from 0 to the number of players - 1
    int player = randRange(0, num_players - 1);
    // Kingdom card set
    int kc[NUM_K_CARDS];
    // Number to set to '1' if random state includes the mandatory kingdom card
    int has_mandatory_card = 0;
    int card_type = get_card_type(mandatory_card);
    int i;

    // Borrowed from interface.c
    //selectKingdomCards(Random(), kc);
    selectKingdomCards(1, kc);

    // Check that mandatory_card is in the deck.
    // We only need to worry about kingdom cards; all the rest are included by
    // default.
    if(card_type == kingdom_t) {
        for(i = 0; i < NUM_K_CARDS; i++) {
            if(kc[i] == mandatory_card) {
                has_mandatory_card = 1;
                break;
            }
        }
        // If mandatory kc_is not in the deck, place it there.
        if(! has_mandatory_card) {
            kc[randRange(0, NUM_K_CARDS - 1)] = mandatory_card;
        }
    }

    // Make sure that our randomly-generated game is 'valid' by the terms of
    // is_valid_game_state(), and that our player has the right card in hand.
    while(! is_valid_game_state(state)
            || count_cards(state->hand[player], state->handCount[player], mandatory_card) < 1) {
        // Erase previous state
        memset(state, 0, sizeof(struct gameState));

        // Initialize the game
        initializeGame(num_players, kc, 2, state);

        // shuffle all the cards
        shuffle_game(player, state);

        for(i = 0; i < HANDSIZE; i++)
            drawCard(player, state);
    }

#ifndef NDEBUG
    char card_name[MAX_STRING_LENGTH];
    printf("Number of players: %d\n", num_players);
    for(i = 0; i < num_players; i++) {
        printf("Hand count for player %d: %d\n", i+1, state->handCount[i]);
        printf("Deck count for player %d: %d\n", i+1, state->deckCount[i]);
        printf("Discard count for player %d: %d\n", i+1, state->discardCount[i]);
    }

    for(i = 0; i < NUM_TOTAL_K_CARDS; i++) {
        cardNumToName(i, card_name);
        printf("Number of %s cards: %d\n", card_name, state->supplyCount[i]);
    }
#endif

    state->whoseTurn = player;
    state->phase = phase;
}

int get_card_type(int card)
{
    switch(card) {
        case curse:
            return curse_t;
        case estate:
            return victory_t;
        case duchy:
            return victory_t;
        case province:
            return victory_t;
        case copper:
            return treasure_t;
        case silver:
            return treasure_t;
        case gold:
            return treasure_t;
        case adventurer:
            return kingdom_t;
        case council_room:
            return kingdom_t;
        case feast:
            return kingdom_t;
        case gardens:
            return victory_t;
        case mine:
            return kingdom_t;
        case remodel:
            return kingdom_t;
        case smithy:
            return kingdom_t;
        case village:
            return kingdom_victory_t;
        case baron:
            return kingdom_t;
        case great_hall:
            return kingdom_victory_t;
        case minion:
            return kingdom_t;
        case steward:
            return kingdom_t;
        case tribute:
            return kingdom_t;
        case ambassador:
            return kingdom_t;
        case cutpurse:
            return kingdom_t;
        case embargo:
            return kingdom_t;
        case outpost:
            return kingdom_t;
        case salvager:
            return kingdom_t;
        case sea_hag:
            return kingdom_t;
        case treasure_map:
            return kingdom_t;
        default:
            return -1;
    }
}

int is_valid_game_state(struct gameState *state)
{
    char card_name[MAX_STRING_LENGTH];
    int i, j;
    int card_count;
    int kingdom_card_instances = 0;
    int card_type;
    int card_counts[NUM_TOTAL_K_CARDS];
    int num_players;
    int num_added_v_cards;
    // Set initial count
    memset(card_counts, 0, NUM_TOTAL_K_CARDS * sizeof(int));

    // Loop through all players' decks, hands, and discard piles, counting how
    // many of each card appears
    for(i = 0; i < state->numPlayers; i++) {
        for(j = 0; j < state->deckCount[i]; j++)
            card_counts[state->deck[i][j]]++;
        for(j = 0; j < state->handCount[i]; j++)
            card_counts[state->hand[i][j]]++;
        for(j = 0; j < state->discardCount[i]; j++)
            card_counts[state->discard[i][j]]++;
    }

    // Count the cards in the supply piles
    for(i = 0; i < NUM_TOTAL_K_CARDS; i++)
        card_counts[i] += state->supplyCount[i];


    // Loop through the counted cards, making sure that all numbers jibe with
    // the Dominion rules
    for(i = 0; i < NUM_TOTAL_K_CARDS; i++) {
        card_count = card_counts[i];
        card_type = get_card_type(i);
        num_players = state->numPlayers;

        cardNumToName(i, card_name);

        switch(card_type) {
            case treasure_t:
                break;
            case kingdom_t:
                if(card_count == -1)
                    break;
                if(card_count == NUM_K_CARDS) {
                    // We keep track of the instances, because there should be
                    // only 10 types of kindom/kingdom_victory cards in play
                    kingdom_card_instances++;
                } else {
                    log_info("Incorrect number of %s cards for 2 players: %d", card_name, card_count);
                    return 0;
                }
                break;
            case kingdom_victory_t:
                if(card_count == -1)
                    break;
                if(num_players == 2) {
                    if(card_count == NUM_V_CARDS_2) {
                        // We keep track of the instances, because there should be
                        // only 10 types of kindom/kingdom_victory cards in play
                        kingdom_card_instances++;
                    } else {
                        log_info("Incorrect number of %s cards for 2 players: %d", card_name, card_count);
                        return 0;
                    }
                } else {
                    if(card_count == NUM_V_CARDS_3or4) {
                        kingdom_card_instances++;
                    } else {
                        log_info("Incorrect number of %s cards for 3 or 4 players: %d", card_name, card_count);
                        return 0;
                    }
                }
                break;
            case victory_t:
                num_added_v_cards = i == estate ? START_ESTATE * num_players : 0;
                if(num_players == 2) {
                    if(card_count != NUM_V_CARDS_2 + num_added_v_cards) {
                        log_info("Incorrect number of %s cards for 2 players: %d", card_name, card_count);
                        return 0;
                    }
                } else {
                    if(card_count != NUM_V_CARDS_3or4 + num_added_v_cards) {
                        log_info("Incorrect number of %s cards for 3 or 4 players: %d", card_name, card_count);
                        return 0;
                    }
                }
                break;
            case curse_t:
                // Number of curse cards is 10 per (players - 1)
                if(card_count != (10 * (state->numPlayers - 1))) {
                    log_info("Incorrect number of %s cards: %d", card_name, card_count);
                    return 0;
                }
                break;
            default:
                log_info("Not a valid card type: %d", card_type);
                return 0;
        }
    }

    // Phew!
    return isGameOver(state);
}

int ops_hand_counts(int player, struct gameState *state)
{
    int i;
    int res = 0;

    for(i = 0; i < state->numPlayers; i++)
        if(i != player) {
            res += state->handCount[i];
        }

    return res;
}

void fill_array(int *s, int v, size_t n)
{
    while(n--)
        s[n] = v;
}

int ops_deck_counts(int player, struct gameState *state)
{
    int i;
    int res = 0;

    for(i = 0; i < state->numPlayers; i++)
        if(i != player) {
            res += state->deckCount[i];
        }

    return res;
}

int ops_discard_counts(int player, struct gameState *state)
{
    int i;
    int res = 0;

    for(i = 0; i < state->numPlayers; i++)
        if(i != player) {
            res += state->handCount[i];
        }

    return res;
}

void replace_card(int player, struct gameState *state, int from, int to)
{
    int i;

    for(i = 0; i < state->handCount[player]; i++)
        if(state->hand[player][i] == from)
            state->hand[player][i] = to;
}

void iter_deck(int player, struct gameState *state, void (*func)(int))
{
    int i;

    for(i= 0; i < state->deckCount[player]; i++)
        func(state->deck[player][i]);
}

void iter_hand(int player, struct gameState *state, void (*func)(int))
{
    int i;

    for(i= 0; i < state->handCount[player]; i++)
        func(state->hand[player][i]);
}

void iter_discard(int player, struct gameState *state, void (*func)(int))
{
    int i;

    for(i= 0; i < state->discardCount[player]; i++)
        func(state->discard[player][i]);
}

void print_card(int card)
{
    switch(card) {
        case curse:
            printf("curse\n");
            break;
        case estate:
            printf("estate\n");
            break;
        case duchy:
            printf("duchy\n");
            break;
        case province:
            printf("province\n");
            break;
        case copper:
            printf("copper\n");
            break;
        case silver:
            printf("silver\n");
            break;
        case gold:
            printf("gold\n");
            break;
        case adventurer:
            printf("adventurer\n");
            break;
        case council_room:
            printf("council room\n");
            break;
        case feast:
            printf("feast\n");
            break;
        case gardens:
            printf("gardens\n");
            break;
        case mine:
            printf("mine\n");
            break;
        case remodel:
            printf("remodel\n");
            break;
        case smithy:
            printf("smithy\n");
            break;
        case village:
            printf("village\n");
            break;
        case baron:
            printf("baron\n");
            break;
        case great_hall:
            printf("great hall\n");
            break;
        case minion:
            printf("minion\n");
            break;
        case steward:
            printf("steward\n");
            break;
        case tribute:
            printf("tribute\n");
            break;
        case ambassador:
            printf("ambassador\n");
            break;
        case cutpurse:
            printf("cutpurse\n");
            break;
        case embargo:
            printf("embargo\n");
            break;
        case outpost:
            printf("outpost\n");
            break;
        case salvager:
            printf("salvager\n");
            break;
        case sea_hag:
            printf("sea hag\n");
            break;
        case treasure_map:
            printf("treasure map\n");
            break;
        default:
            break;
    }
}

int count_in_hand(int player, struct gameState *state, int card)
{
    int i;
    int res = 0;

    for(i= 0; i < state->handCount[player]; i++)
        if(state->hand[player][i] == card) {
            res++;
        }

    return res;
}

int randRange(int lhs, int rhs)
{
    SelectStream(DEFAULT_STREAM);

    int min, max;
    if(lhs < rhs) {
        min = lhs;
        max = rhs;
    } else {
        min = rhs;
        max = lhs;
    }

    int ret = min + floor(Random() * (double)((max - min) + 1));
    return ret;
    //return min + ((int)Random() % ((max - min) + 1));
}

int randCard(void)
{
    return randRange(curse, treasure_map);
}

int numersort(const void *lhs, const void *rhs)
{
    const int *a = (int *)(lhs);
    const int *b = (int *)(rhs);

    return (*a > *b) - (*a < *b);
}

int compare_cards(int *to, int to_count, int *from, int from_count)
{
    int *sm, *lg;
    int sm_count, lg_count;
    int lim;
    int same = 0;
    int sm_index, lg_index;

    // Sort the arrays for faster comparison
    qsort(to, to_count, sizeof(int), numersort);
    qsort(from, from_count, sizeof(int), numersort);

    if(to_count < from_count) {
        sm = to;
        sm_count = to_count;
        lg = from;
        lim = to_count;
    } else {
        sm = from;
        sm_count = from_count;
        lg = to;
        lg_count = to_count;
        lim = from_count;
    }

    for(sm_index = 0, lg_index = 0; sm_index < sm_count && lg_index < lg_count; sm_index++, lg_index++) {
        if(*sm < *lg) {
            lg--;
            lg_index--;
        } else if (*sm > *lg) {
            sm--;
            sm_index--;
        } else {
            same++;
        }
        sm++;
        lg++;
    }

    return lg_count - same;
}
